// import {scan} from './LexParser.js';

let syntax = { // 根据 BNF  参考 abnf 构建语法树
  // Program 最顶层的输入  Statement 声明  StatementList因为用 + 表示不了
  // Non-terminal Symbol 由其他的 Symbol 组合而成  右边为非终结符 
  Program: [['StatementList', 'EOF']], 
  StatementList: [
    ['Statement'],
    ['StatementList', 'Statement']
  ],
  Statement: [
    ['ExpressionStatement'],
    ['IfStatement'],
    ['VariableDeclaration'],
    ['FunctionDeclaration']
  ],
  IfStatement: [
    ['if', '(', 'Expression', ')', 'Statement']
  ],
  VariableDeclaration: [
    ['var', 'Identifier', ';'],
    ['let', 'Identifier', ';']
  ],
  FunctionDeclaration: [ // 暂时只允许没有参数的 function， 函数体里面 又是一个program
    ['function', 'Identifier', '(', ')', '{', 'StatementList', '}']
  ],
  ExpressionStatement: [
    ['Expression', ';']
  ],
  // Expression: [
  //   ['AdditiveExpression'] // 直接这样写是不具备 “写” 的能力
  // ],
  Expression: [
    ['AssignmentExpression']
  ],
  AssignmentExpression: [
    // ['LeftHandSideExpression', '=', 'RightHandSideExpression'],
    // 因为左边一定可以出现在右边，所以AssignmentExpression当作右边
    // ['Identifier', '=', 'AssignmentExpression'],
    ['LeftHandSideExpression', '=', 'LogicalORExpression'],
    // ['AdditiveExpression'] // 四则运算需要一个逻辑
    ['LogicalORExpression']
  ],
  LogicalORExpression: [
    ['LogicalANDExpression'],
    ['LogicalORExpression', '||', 'LogicalANDExpression'],
  ],
  LogicalANDExpression: [
    ['AdditiveExpression'],
    ['LogicalANDExpression', '&&', 'AdditiveExpression'],
  ],
  AdditiveExpression: [ // 加法表示
    ['MultiplicativeExpression'],
    ['AdditiveExpression', '+', 'MultiplicativeExpression'],
    ['AdditiveExpression', '-', 'MultiplicativeExpression']
  ],
  MultiplicativeExpression: [ // 乘法表示
    ['LeftHandSideExpression'],
    ['MultiplicativeExpression', '*', 'LeftHandSideExpression'],
    ['MultiplicativeExpression', '/', 'LeftHandSideExpression']
  ],
  LeftHandSideExpression: [ // 相当于空的逻辑
    ['CallExpression'],
    ['NewExpression']
  ],
  // 以下三个重点注意的是优先级问题
  CallExpression: [ // function.call
    ['MemberExpression', 'Arguments'],
    ['CallExpression', 'Arguments']
  ], // new a()
  NewExpression: [
    ['MemberExpression'],
    ['new', 'NewExpression']
  ], // new a
  MemberExpression: [
    ['PrimaryExpression'],
    ['PrimaryExpression', '.', 'Identifier'],
    ['PrimaryExpression', '[', 'Expression', ']']
  ], // new a.b() 
  PrimaryExpression: [ // 最主要的 也是最小的单元
    ['(', 'Expression', ')']
    ['Literal'],
    // 当声明或访问一些变量时，都需要去存储一些变量
    // 标识符(变量、直接量、常量) Identifier存在哪？存在ExecutionContext
    ['Identifier']
  ],
  Literal: [ // 字面量
    ['NumbericLiteral'], // 七种基本类型 能直接写出来的有四种  Object、Array、Function构造不出来
    ['StringLiteral'],
    ['BooleanLiteral'],
    ['NullLiteral'],
    ['RegularExpression'], // 只是对象的一种特殊的形态
    ['ObjectLiteral'],
    ['ArrayLiteral']
  ],
  ObjectLiteral: [
    ['{', '}'], // 允许为空但有可能出现冲突需要解决
    ['{', 'PropertyList', '}']
  ],
  PropertyList: [
    ['Property'],
    ['PropertyList', ',', 'Property']
  ],
  Property: [
    // ['StringLiteral', ':', 'Expression'] // 这里的Expression是没有','的所以放下一级
    ['StringLiteral', ':', 'AdditiveExpression'],
    ['Identifier', ':', 'AdditiveExpression']
  ]
}

let hash = {} // 用来判断state里是否有相同的结构 避免死循环

function closure(state) { // 求 closure
  // 趁state还没被改变时先存起来
  hash[JSON.stringify(state)] = state
  
  let queue = []
  
  // 展开语法树 也是广度优选搜索的过程
  for (let symbol in state) {
    if(symbol.match(/^\$/)) {
      // return
      continue;
    }
    queue.push(symbol) // 把state上面所有的symbol 存进来
  }

  while(queue.length) { // 广度优选搜索的循环
    let symbol = queue.shift() // 每次先取出来一个 入队 Enqueue 出队 Dequeue
    // console.log(symbol)

    // 拿这个symbol 去语法树里找这个规则
    if(syntax[symbol]) { // 判断 是否是非终结符 终结符不会出现 syntax tree里面
      for(let rule of syntax[symbol]) {
        // console.log(rule[0]) 入队前先判断是否存在
        if(!state[rule[0]]) queue.push(rule[0])

        let current = state // 要把rule里面每一个symbol的部分都连接起来
        for(let part of rule) {
          // 有些sate之间有相同的地方，需要排除
          if(!current[part]) current[part] = {} // current[part]变成一个新的state
          // 前进一位
          current = current[part]
        }
        // 形成一个新的规则
        current.$reduceType = symbol
        current.$reduceLength = rule.length
      }
    }

  }
  // 这一层的已经和之前循环的结构不一样了
  for(let symbol in state) {
    if(symbol.match(/^\$/)) continue; // return
    // console.log(symbol)
    if(hash[JSON.stringify(state[symbol])]) // 判断state是否有
      state[symbol] = hash[JSON.stringify(state[symbol])]
    else closure(state[symbol])
  }

}

// 定义两个状态
let end = {
  $isEnd: true
}

let start = {
  'Program': end
}

closure(start)

export function parse(source) { // 把源代码变成一棵语法树
  let stack = [start] // 先进入开始状态 把每一个state存进栈里面
  let symbolStack = [] // 防止children的顺序错误

  function reduce() {
    let state = stack[stack.length - 1]

    if(state.$reduceType) { // 把存进栈里的状态弹出
      let children = []
      for(let i = 0; i < state.$reduceLength; i++) {
        stack.pop()
        children.push(symbolStack.pop())

      }
        // create a nonterminal symbol and shift it
        // shift({
        //   type: state.$reduceType,
        //   children: children.reverse() // 顺序的相反的要反转一下
        // })
        return {
          type: state.$reduceType,
          children: children.reverse() // 顺序的相反的要反转一下
        }
    } else {
      throw new Error('unexpected token')
    }
  }

  function shift(symbol) { // 处理for循环里的内容可以叫shift
    let state = stack[stack.length - 1] // 每次拿到一个新的状态时 栈顶当成当前状态

    if(symbol.type in state) { // 保存一路的状态
      // console.log(state)
      stack.push(state[symbol.type])
      symbolStack.push(symbol)
    } else {
      /*reduce to non-terminal symbols 合成非终结符 */ 
      // reduce()
      shift(reduce())
      shift(symbol) // 因为实际上symbol还是没有办法存进去，还要再shift一次
    }
  }
 
  for(let symbol/*terminal symbols */ of scan(source)) {
    // console.log(symbol)
    shift(symbol)
  }
  // console.log(state)
  // console.log(reduce())
  return reduce()
}

// parse(source)

// class Realm {
//   constructor() {
//     this.golbal = new Map(),
//     this.Object = new Map(),
//     this.Object.call = function() { // 还包含其他属性 如：execute
//     },
//     this.Object_prototype = new Map()
//   }
// }

// class EnvironmentRecord {
//   constructor() {
//     this.thisValue
//     this.variables = new Map()
//     this.outer = null
//   }
// }

// class ExecutionContext { // 包含存储变量的方法以及 prototype 、var
//   // LexicalEnvironment：{ a:1, b:2} // 词法环境 lexical就是lexer所依赖的环境
//   // global的object 包含三个对象 global对象、Object构造器、Object的原型对象
//   constructor() {
//     this.lexicalEnvironment = {} // 这也不会是一个普通的对象 所以有一个EnvironmentRecord
//     this.variableEnvironment = {} 
//     this.realm = {
//       // golbal: {},
//       // Object: {},
//       // Object_prototype: {}
//     }
//   }
// }

// class Reference {
//   constructor(object, property) {
//     this.object = object
//     this.property = property
//   }
//   get() {
//     return this.object[this.property]
//   }
//   set(value) {
//     this.object[this.property] = value
//   }
// }

// let evaluator = { // 使用对象存储对应的执行方法(运行时)
//   Program(node) {
//     // console.log(node)
//     return evaluate(node.children[0])
//   },
//   StatementList(node) {
//     // console.log(node)
//     if (node.children.length === 1) {
//       return evaluate(node.children[0])
//     } else { // js标准里面的定义
//       evaluate(node.children[0])
//       return evaluate(node.children[1])
//     }
//   },
//   Statement(node) {
//     return evaluate(node.children[0])
//   },
//   VariableDeclaration(node) { // 运行时，变量需要执行
//     // console.log("Declare variable", node.children[1].name)
//     // 取到当前的ExecutionContext
//     let runningEc = ecs[ecs.length - 1] // 栈顶
//     runningEc.variableEnvironment[node.children[1].name]
//   },
//   ExpressionStatement(node) {
//     return evaluate(node.children[0])
//   },
//   Expression(node) {
//     return evaluate(node.children[0])
//   },
//   AdditiveExpression(node) {
//     if(node.children.length === 1)
//       return evaluate(node.children[0])
//     else {
//       // TOOO
//     }
//   },
//   MultiplicativeExpression(node) {
//     if(node.children.length === 1)
//       return evaluate(node.children[0])
//     else {
//       // TOOO
//     }
//   },
//   PrimaryExpression(node) {
//     if(node.children.length === 1)
//       return evaluate(node.children[0])
//   },
//   Literal(node) {
//     return evaluate(node.children[0])
//   },
//   NumbericLiteral(node) { // 处理 number 类型

//     let str = node.value
//     let l = str.length
//     let value = 0
//     let n = 10 // 十进制

//     if (str.match(/^0b/)) { // 判断是否为二进制
//       n = 2
//       l -= 2
//     } else if (str.match(/^0o/)) { // 八进制
//       n = 8
//       l -= 2
//     } else if (str.match(/^0x/)) { // 十六进制
//       n = 16
//       l -= 2
//     }

//     while(l--) { // '0'.charCodeAt(0) 得到0位的码点
//       let c = str.charCodeAt(str.length - l - 1)
//       if(c >= 'a'.charCodeAt(0)) {
//         c = c - 'a'.charCodeAt(0) + 10
//       } else if (c >= 'A'.charCodeAt(0)) {
//         c = c - 'A'.charCodeAt(0) + 10
//       } else if (c >= '0'.charCodeAt(0)) {
//         c = c - '0'.charCodeAt(0)
//       }

//       value = value * n + c
//       // value = value * n * str.charCodeAt(str.length - l - 1) - '0'.charCodeAt(0)
//     }

//     return Number(node.value)
//     // return evaluate(node.children[0])
//   },
//   StringLiteral(node) { // 不去做 utf-16的处理
//     // console.log(node.value)
//     let i = 1
//     let result = []

//     for (let i = 1; i < node.value.length - 1; i++) {
//       if (node.value[i] === '\\') { // 转义
//         ++ i
//         let c = node.value[i]
//         let map = { // 默认BMP 用一个UTF-16的表示的000000~ffffff
//           "\"": "\"",
//           "\'": "\'",
//           "\\": "\\",
//           "0": String.fromCharCode(0x0000),
//           "b": String.fromCharCode(0x0008),
//           "f": String.fromCharCode(0x000C),
//           "n": String.fromCharCode(0x000A),
//           "r": String.fromCharCode(0x000D),
//           "t": String.fromCharCode(0x0009),
//           "v": String.fromCharCode(0x000B)
//         }
//         if (c in map) { // 如果存在
//           result.push(map[c])
//         } else {
//           result.push(c)
//         }
//       } else {
//         result.push(node.value[i])
//       }
//     }
//     console.log(result)
//     return result.join('')
//   },
//   ObjectLiteral(node) {
//     if(node.children.length === 2)
//       return {};
//     if(node.children.length === 3) { // kv对 Object包含property和原型两部分
//       let object = new Map() // 用map类型来保存property部分
//       this.PropertyList(node.children[1], object) // [0]、[2]都是花括号
      
//       // object.prototype = 
//       return object
//     }
//   },
//   PropertyList(node, object) {
//     if(node.children.length === 1) {
//       this.Property(node.children[0], object)
//     } else { // 如果有多个可以递归
//       this.PropertyList(node.children[0], object) // [1]是逗号
//       this.Property(node.children[2], object)
//     }
//   },
//   Property(node, object) {
//     let name; // 处理两种类型
//     if (node.children[0].type === 'Identifier') {
//       name  = node.children[0].name
//     } else if (node.children[0].type === 'StringLiteral') {
//       name = evaluate(node.children[0])
//     }
//     // object.set(evaluate(node.children[0]), evaluate(node.children[2]))
//     object.set(name, { // 一个kv对不能直接单单写值，还要有属性
//       value: evaluate(node.children[2]),
//       writable: true,
//       enumerable: true,
//       configurable: true
//     })
//   },
//   AssignmentExpression(node) {
//     if(node.children.length === 1)
//       return evaluate(node.children[0]);
//     let left = evaluate(node.children[0]);
//     let right = evaluate(node.children[2]);
//     left.set(right) // 认为左边的值是一个Reference类型
//   },
//   Identifier(node) {
//     // 取到当前的ExecutionContext
//     let runningEc = ecs[ecs.length - 1] // 栈顶
//     // return runningEc.lexicalEnvironment[node.name] // 取变量(直接取是比较草率的，不应只读)
//     // 用一个Reference 类型把属性值与名存起来
//     return new Reference(runningEc.lexicalEnvironment, node.name)
//   }
//   // EOF() {
//   //   return null
//   // }

// }

// // 是在JS引擎的一个新实例被建立起来的时候产生的
// let realm = new Realm()
// // 每次函数调用时有一个栈来管理ExecutionContext
// let ecs = [new ExecutionContext]

// function evaluate(node) { // 逐级的执行语法树 语义分析
//   // console.log(node)
//   if (evaluator[node.type]) {
//     let r = evaluator[node.type](node)
//     console.log(r)
//     return r
//   }
// }

// --------------------------------------------------------------------
// 7788 \ 0b1101 \ 0xFF \ 
// let source = `
//   "ab\\bc"
// `

// let tree = parse(source)

// evaluate(tree)

// 需要保存到window里面 否则访问不到
// window.js = {
//   evaluate, parse
// };

